#include <iostream>
#include <deque>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
private:
    void divide(ListNode* head, ListNode*& first, ListNode*& second) {
        first = head;
        second = head->next;
        while (second != nullptr && second->next != nullptr) {
            first = first->next;
            second = second->next->next;
        }
        second = first->next;
        first->next = nullptr;
        first = head;
    }
    ListNode* merge(ListNode* first, ListNode* second) {
        ListNode* head = nullptr;
        if (first->val < second->val) {
            head = first;
            first = first->next;
        } else {
            head = second;
            second = second->next;
        }
        ListNode* ptr = head;
        while (first != nullptr && second != nullptr) {
            if (first->val < second->val) {
                ptr->next = first;
                first = first->next;
            } else {
                ptr->next = second;
                second = second->next;
            }
            ptr = ptr->next;
        }
        while (first != nullptr) {
            ptr->next = first;
            ptr = ptr->next;
            first = first->next;
        }
        while (second != nullptr) {
            ptr->next = second;
            ptr = ptr->next;
            second = second->next;
        }
        ptr->next = nullptr;
        return head;
    }
    ListNode* helper(ListNode* head) {
        if (head->next == nullptr) {
            return head;
        }
        ListNode* first = nullptr;
        ListNode* second = nullptr;
        divide(head, first, second);
        first = helper(first);
        second = helper(second);
        ListNode* sort = merge(first, second);
        return sort;
    }
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        return helper(head);
    }
};


int main() {
    ListNode l1(3), l2(2), l3(0), l4(-4);
    l1.next = &l2;
    l2.next = &l3;
    l3.next = &l4;
    l4.next = NULL;
    Solution solution;
    solution.sortList(&l1);
    return 0;
}